package array;

import java.util.Arrays;

/**
 * 缺失的第一个正数
 */
public class E017firstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if(nums[i] <= 0) nums[i] = n + 1;
        }
        for (int i = 0; i < n; i++) {
            //nums[i] 可能已经被设为负
            int num = Math.abs(nums[i]);
            if(num <= n){
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if(nums[i] > 0) return i+1;
        }
        return n+1;
    }
}
